package leetcode.editor.cn;

//给定一个已排序的链表的头
// head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。 
//
// 
//
// 示例 1： 
// 
// 
//输入：head = [1,1,2]
//输出：[1,2]
// 
//
// 示例 2： 
// 
// 
//输入：head = [1,1,2,3,3]
//输出：[1,2,3]
// 
//
// 
//
// 提示： 
//
// 
// 链表中节点数目在范围 [0, 300] 内 
// -100 <= Node.val <= 100 
// 题目数据保证链表已经按升序 排列 
// 
//
// Related Topics 链表 👍 926 👎 0

import java.util.HashSet;
import java.util.Set;

class RemoveDuplicatesFromSortedList{
    public static void main(String[] args) {
    	
        Solution solution = new RemoveDuplicatesFromSortedList().new Solution();
        ListNode head = new ListNode(-1);
        ListNode pre=head;
        new ListNode(-1);
        for (int i : new int[]{1, 1, 2, 3, 3}) {
            ListNode node = new ListNode(i);
            pre.next=node;
            pre=pre.next;
        }
        ListNode head1=solution.deleteDuplicates(head.next);
        
    }

//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        /*1，设置一个set 保存每一个节点的val值
         * 遍历链表，
         * while（节点。next不为空）
         *   if（节点。next的值在set中）
         *       删除当前节点的下一个节点
         *   else  节点=节点。next*/
        HashSet<Integer> set = new HashSet<>();
        ListNode pre=head;

        if(head!=null){
            set.add(head.val);//头节点值保存在里面
            while(pre.next!=null){
                if(set.contains(pre.next.val)){
                    //del
                    pre.next=pre.next.next;
                }
                else{
                    set.add(pre.next.val);
                    pre=pre.next;
                }
            }

        }
        return head;


    }
}


//leetcode submit region end(Prohibit modification and deletion)

}
